perm filename A31.TEX[106,RWF] blob
sn#872423 filedate 1989-04-21 generic text, type C, neo UTF8
COMMENT ā VALID 00002 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 \magnification\magstephalf
C00010 ENDMK
Cā;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
January\or February\or March\or April\or May\or June\or
July\or August\or September\or October\or November\or December\fi
\space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a31.tex[106,phy] \today\hfill}
\bigskip
{\rmn
{\narrower\smallskip\noindent
{\bf Exercise.}
\noindent
The diagrams below show several orders in which a program might process
some of the elements of an array, perhaps by reading into them or
printing them. For example, according to the second diagram the
program is to do something successively to $A[1,1],A[2,1],A[2,2]$,
$A[3,1],\ldots,A[5,5]$.
For each diagram, find a driver that executes
command~$S$ repeatedly, giving $R$ and~$C$ values such that when~$S$
is executed $A[R,C]$ is the correct array element for it to process.
\smallskip}
}
$$\vbox{\offinterlineskip
\halign{\hfil#\hfil\qquad&\hfil#\hfil\quad&\vrule#&\strut\quad\hfil#\quad%
&\hfil#\quad&\hfil#\quad&\hfil#\quad&\hfil#\quad&\vrule#\cr
&&\omit&1&2&3&4&5\cr
\noalign{\smallskip}
&&\multispan6\hrulefill\cr
&&height2pt&\omit&\omit&\omit&\omit&\omit&\cr
(1)&1&&1&&&&&\cr
&2&&2&3&&&&\cr
&3&&4&5&6&&&\cr
&4&&7&8&9&10&&\cr
&5&&11&12&13&14&15&\cr
&&height2pt&\omit&\omit&\omit&\omit&\omit&\cr
&&\multispan6\hrulefill\cr}}
\qquad\qquad
\vbox{\offinterlineskip
\halign{\hfil#\hfil\qquad&\hfil#\hfil\quad&\vrule#&\strut\quad\hfil#\quad%
&\hfil#\quad&\hfil#\quad&\hfil#\quad&\hfil#\quad&\vrule#\cr
&&\omit&1&2&3&4&5\cr
\noalign{\smallskip}
&&\multispan6\hrulefill\cr
&&height2pt&\omit&\omit&\omit&\omit&\omit&\cr
(2)&1&&1&2&3&4&5&\cr
&2&&10&9&8&7&6&\cr
&3&&11&12&13&14&15&\cr
&4&&20&19&18&17&16&\cr
&5&&21&22&23&24&25&\cr
&&height2pt&\omit&\omit&\omit&\omit&\omit&\cr
&&\multispan6\hrulefill\cr
}}$$
$$\vbox{\offinterlineskip
\halign{\hfil#\hfil\quad&\hfil#\hfil\quad&\vrule#&\strut\quad\hfil#\quad%
&\hfil#\quad&\hfil#\quad&\hfil#\quad&\hfil#\quad%
&\hfil#\quad&\hfil#\quad&\hfil#\quad&\hfil#\quad&\vrule#\cr
&&\omit&1&2&3&4&5&6&7&8&9\cr
\noalign{\smallskip}
&&\multispan{10}\hrulefill\cr
&&height2pt&\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit&\cr
(3)&1&&&&&&1&&&&&\cr
&2&&&&&4&3&2&&&&\cr
&3&&&&5&6&7&8&9&&&\cr
&4&&&16&15&146&13&12&11&10&&\cr
&5&&17&18&19&20&21&22&23&24&25&\cr
&&height2pt&\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit&\cr
&&\multispan{10}\hrulefill\cr
}}
\qquad
\vbox{\offinterlineskip
\halign{\hfil#\hfil\quad&\hfil#\hfil\quad&\vrule#&\strut\quad\hfil#\quad%
&\hfil#\quad&\hfil#\quad&\hfil#\quad&\hfil#\quad&\vrule#\cr
&&\omit&1&2&3&4&5\cr
\noalign{\smallskip}
&&\multispan6\hrulefill\cr
&&height2pt&\omit&\omit&\omit&\omit&\omit&\cr
(4)&1&&1&2&3&4&5&\cr
&2&&16&17&18&19&6&\cr
&3&&15&24&25&20&7&\cr
&4&&14&23&22&21&8&\cr
&5&&13&12&11&10&9&\cr
&&height2pt&\omit&\omit&\omit&\omit&\omit&\cr
&&\multispan6\hrulefill\cr
}}$$
\bigskip
{\rmn
{\narrower\smallskip\noindent
{\bf Solution.}
\noindent
{\obeylines\obeyspaces\let =\ \tt
{\rm(1)} R:=1; C:=1;
WHILE R<6 DO
BEGIN
S;
IF C=R THEN
BEGIN
C:=1;
R:=R+1
END
ELSE C:=C+1
END
}
\vfill\eject
\noindent
{\obeylines\obeyspaces\let =\ \tt
{\rm(2)} R:=1; C:=1; STEP:=1;
FOR I:=1 TO 25 DO
BEGIN
S;
IF I MOD 5=0 THEN
BEGIN
R:=R+1;
STEP:=-STEP
END
ELSE C:=C+STEP
END
}
\noindent
{\obeylines\obeyspaces\let =\ \tt
{\rm(3)} C:=5; STEP:=1;
FOR R:=1 TO 5 DO
BEGIN
FOR I:=1 TO 2*R-1 DO
BEGIN
S;
C:=C+STEP;
END;
STEP:=-STEP
END
}
\noindent
{\obeylines\obeyspaces\let =\ \tt
{\rm(4)} BEGIN
R:=1; C:=1; LENGTH:=4; RSTEP:=0; CSTEP:=1;
WHILE LENGTH>0 DO
BEGIN
FOR DIRECTION:=1 TO 4 DO
BEGIN
FOR COUNT:=1 TO LENGTH DO
BEGIN
S;
R:=R+RSTEP; C:=C+CSTEP;
END;
TEMP:=-RSTEP; RSTEP:=CSTEP; CSTEP:=TEMP;
END;
LENGTH:=LENGTH-2;
R:=R+1; C:=C+1;
END;
S (* CENTER IS AN EXCEPTION *)
END
}
\smallskip}
}
\bigskip
\parindent0pt
\copyright 1984 Robert W. Floyd
First draft September 10, 1984
\bye